﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Server.Controller.Graph
{
    public class PriorityQueueLinkedList<T> : IPriorityQueue<T> where T : IComparable
    {

        private LinkedList<T> _list;

        // Constructor is initializing the LinkedList.
        public PriorityQueueLinkedList() {
            _list = new LinkedList<T>();
        }

        // Adds a element to the end of the linked list.
        public void queue(T t)
        {
            _list.AddLast(t);
        }

        // Complexity O(n)! Faktisk O(2n) worst case, O(n) best case
        // ---------------------------------------------------------
        // Loops through a list finding the item, with lowest value. 
        // Removes 'lowest' item from the list and returns it.
        public T dequeue()
        {
            // Sets 'lowest' to default. 
            // For a numeric type value is "0", for a complex type value is "null".
            T lowest = default(T);
            
            // Starting the loop
            foreach (T item in _list)
            {
                // If 'lowest' is null beacause of first run through, set new item.
                if (lowest == null)
                {
                    lowest = item;
                }

                // if item < lowest, set new lowest.
                if (item.CompareTo(lowest)<0)
                {
                    lowest = item;
                }
            }
            // Remove 'lowest' item from list.
            _list.Remove(lowest);

            // Return 'lowest' item
            return lowest;
        }

        // Counts the total number of nodes in the list.
        public int count()
        {
            return _list.Count();
        }

        // Clears the list.
        public void clear()
        {
            _list.Clear();
        }

        // If _list is empty returns "true", if not empty returns "false".
        public bool isEmpty()
        {
            return (_list.Count == 0);
        }
    }
}
